#pragma once
#include "PolynomialResidue.h"
#include "Residue.h"
#include "ResidueField.h"
#include "Rational.h"
#include <utility>

namespace NumberTheory
{
	Integer GCD(const Integer &x, const Integer &y);
	Integer LCM(const Integer &x, const Integer &y);
	Integer ExGCD(const Integer &x, const Integer &y, Integer &a, Integer &b);
	template <typename T> Polynomial<T> GCD(const Polynomial<T> &poly1, const Polynomial<T> &poly2);
	Polynomial<Integer> GCD(const Polynomial<Integer> &poly1, const Polynomial<Integer> &poly2);
	int Legendre_Jacobi_Kronecker(const Integer &x, const Integer &y);
	bool IsProbablyPrime(const Integer &n);
	bool IsPrime(const Integer &n);
	bool IsComposite(const Integer &n);
	Integer FindFactor(const Integer &n);
	std::vector<std::pair<Integer, unsigned>> Factor(const Integer &n);
	std::vector<std::pair<Integer, int>> Factor(const Rational &r);
	std::vector<std::pair<Polynomial<ResidueField>, unsigned>> Factor(const Polynomial<ResidueField> &poly);
	std::vector<std::pair<Polynomial<Integer>, unsigned>> Factor(const Polynomial<Integer> &poly);
	std::string PrintFactor(const Integer &n);
	unsigned DivisorCount(const Integer &n);
	Integer DivisorSum(const Integer &n);
	Integer EulerPhi(const Integer &n);
	int Mobius(const Integer &n);
}

template <typename T> Polynomial<T> NumberTheory::GCD(const Polynomial<T> &poly1, const Polynomial<T> &poly2)
{
	if (poly1 == Polynomial<T>() && poly2 == Polynomial<T>())
		return Polynomial<T>();
	else if (poly1 == Polynomial<T>())
		return poly2 / poly2.LeadingCoefficient();
	else if (poly2 == Polynomial<T>())
		return poly1 / poly1.LeadingCoefficient();

	if (Degree(poly1) < Degree(poly2))
		return GCD(poly2 % poly1, poly1);
	else
		return GCD(poly1 % poly2, poly2);
}
